# 给你一个字符串 s，找到 s 中最长的回文子串。
# 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
#
# 示例 1：
# 输入：s = "babad"
# 输出："bab"
# 解释："aba" 同样是符合题意的答案。
#
# 示例 2：
# 输入：s = "cbbd"
# 输出："bb"
#
# 提示：
# 1 <= s.length <= 1000
# s 仅由数字和英文字母组成
def wu(s):
    n = len(s)
    dp = [[False] * n for _ in range(n)]
    start, max_length = 0, 1

    # 单个字符一定是回文
    for i in range(n):
        dp[i][i] = True

    # 两个相邻字符相同则为回文
    for i in range(n-1):
        if s[i] == s[i+1]:
            dp[i][i+1] = True
            start = i
            max_length = 2

    # 从长度为3的子串开始遍历
    for length in range(3, n+1):
        for i in range(n-length+1):
            j = i + length - 1
            if s[i] == s[j] and dp[i+1][j-1]:
                dp[i][j] = True
                start = i
                max_length = length

    return s[start:start+max_length]

# 测试
s = "babad"
print(wu(s))  # 输出 "bab" 或 "aba"


